package 二叉树;


//https://leetcode-cn.com/problems/binode-lcci/
//TODO 没有完全理解
public class 面试题17_12_BiNode {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    //定义一个全局的指针
    TreeNode node;
    public TreeNode convertBiNode(TreeNode root) {
        //实例化指针
        node = new TreeNode(0);
        //备份这个指针
        TreeNode temp = node;
        inorder(root);
        //返回二叉树的第一个节点
        return temp.right;
    }

    private void inorder(TreeNode root) {
        //跳出递归的条件
        if(root == null) return;
        //中序遍历
        inorder(root.left);
        //将root放到链表的最后
        node.right = root;
        //将二叉树的所以left节点==null
        root.left = null;
        //指向头指针的最后一个节点
        node = node.right;
        inorder(root.right);
    }
    /*public TreeNode convertBiNode(TreeNode root) {
        //声明一个链表指针，指向头节点
        TreeNode head = new TreeNode(0);
        //中序递归遍历
        inorder(root,head);
        return head.right;
    }

    private TreeNode inorder(TreeNode root, TreeNode head) {
        while (root != null){
            //root的左子树
            head = inorder(root.left,head);
            root.left = null;
            //根节点
            head.right = root;
            //root的右子树
            head = root;
            head= inorder(root.right,head);
        }
        return head;
    }*/
}
